// Dynamic Array
// (c) jimon game studio

#ifndef JEH_JEDYNAMICARRAY
#define JEH_JEDYNAMICARRAY

#include "jeTypes.h"
#include "jeMemory.h"
#include "jeDebug.h"
#include "jeMath.h"
#include "IBuffer.h"
#include <malloc.h>
#include <memory.h>
#include <string.h>

#ifdef JE_DYNAMICARRAY_OPTIMALSORT
#include "ITimer.h"
#endif

namespace je
{
	//! Dynamic Array
	template<typename T>
	class jeDynamicArray
	{
	public:
		//! Sort Compare Function Type, return 1 if Elem1 > Elem2, 2 if Elem1 < Elem2,4 if Elem1 == Elem2
		typedef u8 (*jeSortCompareFunction)(T Elem1,T Elem2);

	protected:
		T * Array;
		u32 Size;
		u32 BlockCount;
		u32 CurrentReserveBlockSize;

		void DownHeap(jeSortCompareFunction Func,u32 i,u32 n)
		{
			for(u32 k=i+1;k<n;i++,k+=2)
			{
				if (k==n-1)
				{
					if(Func(Array[k],Array[i])==1)
						Swap(k,i);
				}
				else
					Swap(i,(Func(Array[i],Array[k])==1)?(Func(Array[i],Array[k+1])==1?i:k+1):(Func(Array[k],Array[k+1])==1?k:k+1));
			}
		}

		void QuickSortRec(jeSortCompareFunction Func,u32 Left,u32 Right) // TODO check rights s32\u32
		{
			u32 LHold = Left,RHold = Right;
			T Pivot = Array[Left];
			while(Left < Right)
			{
				while((Func(Array[Right],Pivot)!=2) && (Left < Right))
					Right--;
				if(Left!=Right)
				{
					Array[Left] = Array[Right];
					Left++;
				}
				while((Func(Array[Right],Pivot)!=1) && (Left < Right))
					Left++;
				if(Left!=Right)
				{
					Array[Right] = Array[Left];
					Right--;
				}
			}
			Array[Left] = Pivot;
			if(LHold < Left)
				QuickSortRec(Func,LHold,Left-1);
			if(RHold > Left)
				QuickSortRec(Func,Left+1,RHold);
		}

		//! if delta = false mean -1, delta = true - +1
		void ReSizeArray(u1 Delta,u32 Index,u1 EnableIndex)
		{
			if(Delta)
			{
				if(++Size>CurrentReserveBlockSize*BlockCount)
					if(Array)
						Array = reinterpret_cast<T*>(realloc(Array,sizeof(T)*(CurrentReserveBlockSize*++BlockCount)));
					else
						Array = reinterpret_cast<T*>(malloc(sizeof(T)*(CurrentReserveBlockSize*++BlockCount)));

				if(EnableIndex)
					memmove(Array+Index+1,Array+Index,(Size-Index-1)*sizeof(T));
			}
			else
			{
				if(Size == 0)
					return;
				
				if(--Size == 0)
				{
					BlockCount = 0;
					free(Array);
					Array = NULL;
				}
				else
				{
					if(EnableIndex)
						memmove(Array+Index,Array+Index+1,(Size-Index)*sizeof(T));

					if(Size<=CurrentReserveBlockSize*(BlockCount-1))
						Array = reinterpret_cast<T*>(realloc(Array,sizeof(T)*(CurrentReserveBlockSize*--BlockCount)));
				}
			}
		}

		#ifdef JE_DYNAMICARRAY_OPTIMALSORT
		f32 SortTime_Quick,SortTime_Heap,SortTime_Shell,LastPenaltyTime;
		#endif

	public:
		//! Constructor
		jeDynamicArray(s32 ReserveBlockSize = JE_DYNAMICARRAY_OPTIMALBLOCKSIZE)
			:Array(NULL),Size(0),BlockCount(0),CurrentReserveBlockSize(ReserveBlockSize)
		{
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Quick = 0.0f;
			SortTime_Heap = 0.0f;
			SortTime_Shell = 0.0f;
			if(core::GetTimer())
				LastPenaltyTime = JETIME + rand()%JE_DYNAMICARRAY_PENALTYDELTATIME; //if we create a lot of dynamic arrays in one time, we really dont want to review all sort alg. in one time
			else
				LastPenaltyTime = 0.0f;
			#endif
		}

		//! Destructor
		~jeDynamicArray()
		{
			Clear();
		}

		//! Insert Element at end
		void InsertElement(T Object)
		{
			ReSizeArray(true,0,false);
			Array[Size-1] = Object;
		}

		//! Insert Element
		void InsertElement(T Object,u32 Index)
		{
			ReSizeArray(true,Index,true);
			Array[Index] = Object;
		}

		//! Insert Block
		void InsertBlock()
		{
			ReSizeArray(true,0,false);
		}

		//! Insert Block
		void InsertBlock(u32 Index)
		{
			ReSizeArray(true,Index,true);
		}

		//! Erase Element
		void EraseElement(u32 Index)
		{
			if(Index == (Size-1))
				ReSizeArray(false,0,false);
			else
				ReSizeArray(false,Index,true);
		}

		//! Swap
		void Swap(u32 IndexA,u32 IndexB)
		{
			T ObjTemp = Array[IndexA];
			Array[IndexA] = Array[IndexB];
			Array[IndexB] = ObjTemp;
		}

		//! Clear
		void Clear()
		{
			if(Array)
			{
				free(Array);
				Array = NULL;
			}
			Size = 0;
			BlockCount = 0;
		}

		//! Get Size
		u32 GetSize() const
		{
			return Size;
		}
		
		//! Get Block Count
		u32 GetBlockCount() const
		{
			return BlockCount;
		}

		//! Get Block Size
		u32 GetBlockSize() const
		{
			return CurrentReserveBlockSize;
		}

		//! Linear Search
		u1 LinearSearch(const T & Object,u32 & Result)
		{
			for(u32 i=0;i<Size;i++)
				if(Array[i] == Object)
				{
					Result = i;
					return true;
				}
			return false;
		}

		//! Quick Sort
		void QuickSort(jeSortCompareFunction Func)
		{
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Quick = JETIME;
			#endif
			QuickSortRec(Func,0,Size-1);
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Quick = JETIME - SortTime_Quick;
			#endif
		}

		//! Heap Sort
		void HeapSort(jeSortCompareFunction Func)
		{
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Heap = JETIME;
			#endif
			u32 i = Size/2,n = Size;
			while(i-- > 0)
				DownHeap(Func,i,Size);
			while(--n > 0)
			{
				Swap(0,n);
				DownHeap(Func,0,n);
			}
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Heap = JETIME - SortTime_Heap;
			#endif
		}

		//! Shell Sort
		void ShellSort(jeSortCompareFunction Func)
		{
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Shell = JETIME;
			#endif
			u32 h=1;
			while(h<=Size/9)
				h=3*h+1;
			while(h>0)
			{
				for(u32 i=h;i<Size;i++)
				{
					u32 j;
					T Save = Array[i];
					for(j=i;j>=h&&(Func(Array[j-h],Save)==1);j>=h?j-=h:j=0) // TODO check j=0 here
						Array[j]=Array[j-h];
					Array[j]=Save;
				}
				h/=3;
			}
			#ifdef JE_DYNAMICARRAY_OPTIMALSORT
			SortTime_Shell = JETIME - SortTime_Shell;
			#endif
		}

		#ifdef JE_DYNAMICARRAY_OPTIMALSORT
		//! Optimal Sort
		void OptimalSort(jeSortCompareFunction Func)
		{
			(SortTime_Quick<SortTime_Heap)?((SortTime_Quick<SortTime_Shell)?QuickSort(Func):ShellSort(Func)):((SortTime_Heap<SortTime_Shell)?HeapSort(Func):ShellSort(Func));
			f32 Time = JETIME;
			if(Time>(LastPenaltyTime+JE_DYNAMICARRAY_PENALTYDELTATIME))
			{
				LastPenaltyTime = JETIME-rand()%50;
				SortTime_Quick = 0.0f;
				SortTime_Heap = 0.0f;
				SortTime_Shell = 0.0f;
			}
		}
		#endif

		//! Direct Access Operator
		T & operator [](u32 Index)
		{
			return Array[Index];
		}

		//! Direct Access Operator
		const T & operator [](u32 Index) const
		{
			return Array[Index];
		}

		//! Get First
		T & GetFirst()
		{
			return Array[0];
		}

		//! Get Last
		T & GetLast()
		{
			return Array[Size-1];
		}

		//! Get Ptr
		T * GetPtr()
		{
			return Array;
		}

		//! Get Ptr
		const T * GetPtr() const
		{
			return Array;
		}

		//! Copy From
		void CopyFrom(const jeDynamicArray<T> & Other)
		{
			Clear();
			Size = Other.GetSize();
			BlockCount = Other.GetBlockCount();
			CurrentReserveBlockSize = Other.GetBlockSize();

			Array = reinterpret_cast<T*>(core::Alloc(sizeof(T)*(CurrentReserveBlockSize*BlockCount)));
			memcpy(Array,Other.GetPtr(),Size*sizeof(T));
		}

		//! Copy From
		void CopyFrom(void * OtherArray,u32 ArraySize)
		{
			Clear();

			if(ArraySize)
			{
				Size = ArraySize / sizeof(T);
				BlockCount = (Size - 1) / CurrentReserveBlockSize + 1;

				Array = reinterpret_cast<T*>(core::Alloc(sizeof(T)*(CurrentReserveBlockSize*BlockCount)));
				memcpy(Array,OtherArray,Size*sizeof(T));
			}
		}

		//! Copy From
		void CopyFrom(core::IBuffer * Buffer,u32 BufferSize)
		{
			Clear();

			if(BufferSize)
			{
				Size = BufferSize / sizeof(T);
				BlockCount = (Size - 1) / CurrentReserveBlockSize + 1;

				Array = reinterpret_cast<T*>(core::Alloc(sizeof(T)*(CurrentReserveBlockSize*BlockCount)));
				Buffer->Read(Array,Size*sizeof(T));
			}
		}
	};
}

#endif
